public class MajorityElement {
    // leetcode 多数元素
    // https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-100-liked

    /**
     * 因为多数元素出现的次数大于n/2，那么candidate初始可以是任何值，然后遍历数组，如果n==candidate，
     * 那么count++，如果n!=candidate，那么count--，如果count==0，candidate=n
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        int candidate = 0, count = 0;
        for (int n : nums) {
            if (count == 0) candidate = n;
            if (candidate == n) count++;
            else count--;
        }
        return candidate;
    }
}
